\documentclass[a4paper]{ctexart}
\usepackage[hidelinks]{hyperref}%目录
\usepackage{xeCJK} %导入这个宏包，就可以支持中文
\usepackage{cite}%文献引用
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{amsthm,amsmath,amssymb,amsfonts}%数学命题，数学字母，排版
\usepackage[a4paper,left=25.4mm,right=25.4mm,top=29.8mm,bottom=29.8mm]{geometry}

\pagestyle{myheadings}
\numberwithin{equation}{section}%以section编号equation



%数学命题环境定义 
%证明环境直接用proof
\theoremstyle{plain} \newtheorem{thm}{定理}[section]
\theoremstyle{plain} \newtheorem*{lemma}{引理}
\theoremstyle{plain} \newtheorem*{prop}{prop}
\theoremstyle{plain} \newtheorem*{property}{性质}
\theoremstyle{definition} \newtheorem*{define}{定义}
\theoremstyle{plain} \newtheorem*{cor}{cor}
\theoremstyle{plain} \newtheorem{eg}{例}[section]
\theoremstyle{plain} \newtheorem{axiom}{公理}
\theoremstyle{remark} \newtheorem*{rmk}{算例}
\theoremstyle{plain} \newtheorem*{goal}{Goal}



\title{Sorting}
\author{陈宇涛，强数2101,3210102287}


\begin{document}
\maketitle

\section{作业要求}
\begin{flushleft}
    测试课本提供的heapsort 和quicksort的排序效率， 比较二者在百分之1,10,90,99的输入数据有序的前提下的排序效率. 测试数据请自己按要求产生, 测试数组n不小于10000, 每个n 请用多组数据反复测试.
\end{flushleft}




\section{测试说明}
\begin{define}[有序度]
    一个数组a定义升序的有序度为
\[
    P(a)=\frac{\#\left\{  (i,j) ~|~a[i]<a[j],1 \le i <j \le n \right\}}{\#\left\{  (i,j) ~|~1 \le i <j \le n \right\}}
\]

\end{define}    

\begin{flushleft}
    所以所谓创造百分之p的有序度只需要在原先数组升序排列，此时有序度为1，
    随机选择长度为k的区间使得这k个数据降序排列,此时a的有序度即为
    \[
        P(a)=\frac{\binom{k}{2} }{\binom{n}{2} }
    \]
    从而小区间取k为
    \[
        k=\frac{1+\sqrt{1+4p(n^2-n)}}{2}
    \]
\end{flushleft}

\newpage

\begin{flushleft}
    ~\\
    测试结果:\\

当$n=10^{5}$时\\
\begin{table}[!ht]
    \centering
    \begin{tabular}{|l|l|l|l|l|}
    \hline
        排序方式$\backslash$有序度 & 1\% & 10\% & 90\% & 99\% \\ \hline
        heapsort & 0.019427秒 & 0.019404秒 & 0.019311秒 & 0.01968秒\\ \hline
        quicksort & 0.002818秒 & 0.002806秒 & 0.002801秒& 0.002836秒 \\ \hline
    \end{tabular}
\end{table}


当$n=10^{6}$时\\
\begin{table}[!ht]
    \centering
    \begin{tabular}{|l|l|l|l|l|}
    \hline
        排序方式$\backslash$有序度 & 1\% & 10\% & 90\% & 99\% \\ \hline
        heapsort & 0.270928秒 & 0.291235秒 & 0.269984秒 & 0.303117秒 \\ \hline
        quicksort & 0.038636秒 & 0.041587秒 & 0.04232秒& 0.034223秒\\ \hline
    \end{tabular}
\end{table}
\end{flushleft}


\section{优化}
\begin{eg}
    \begin{flushleft}
        调整使用insertionsort的数据规模，原先书上的代码此时取得是10，经过查询计算验证此处大概取20为最优。
    \end{flushleft}

\end{eg}

\begin{eg}
\begin{flushleft}
    将三数中值法换成五数排序中值，经过查询以及计算，此时优于三数中值.
\end{flushleft}

\end{eg}


  
  实际上，提升幅度十分有限，甚至有在很多请况下无法直接比较。
\begin{verbatim}
heapsort 1%运行时间0.19608秒
quicksort 1%运行时间0.02839秒
Newquicksort 1%运行时间0.028254秒
heapsort 10%运行时间0.196345秒
quicksort 10%运行时间0.033533秒
Newquicksort 10%运行时间0.033484秒
heapsort 90%运行时间0.201729秒
quicksort 90%运行时间0.030815秒
Newquicksort 90%运行时间0.031306秒
heapsort 99%运行时间0.197687秒
quicksort 99%运行时间0.030108秒
Newquicksort 99%运行时间0.029817秒
\end{verbatim}



\section{小结}
\begin{flushleft}
    如果从课上的理论分析,有序度不会影响heapsort的效率,但
会影响quicksort的效率.\\
但是我们从上述的两张图表中可以发现,当数据规模为100000和1000000时,有序度
对于quicksort的影响也是不大的。\\

其中最重要的原因是其quicksort运用了三数中值分割法,它使得quicksort中
最差的情况得以完全解决，逆序和顺序变得同样快速。另外当quicksort使用递归时
当数据较小时，直接使用了insertionsort而解决quicksort在此时的短板。\\
\end{flushleft}


\end{document}
